package com.bolang.onlycode.demo;

import com.sun.scenario.effect.impl.sw.java.JSWColorAdjustPeer;

import java.util.ArrayList;
import java.util.Arrays;

public class HeapSort {
    /**
     *
     * @param arr  传进来的数组
     * @param n  数组有几个数
     * @param i  当前把第几个数作为父节点
     */
    public static void heapify(int[] arr,int n,int i){
        if(2*i+1==n){
            return;
        }
        int c1 =2*i+1;
        int c2 =2*i+2;
        int max = i;//假设最大节点是i节点
        if(c1<n&&arr[c1]>arr[max]){
            max=c1;
        }
        if(c2<n&&arr[c2]>arr[max]){
           max=c2;
        }
        if(max!=i){
            swap(arr,max,i);
            heapify(arr,n,max);
        }
    }

    /**
     *
     * @param arr
     * @param n  数组有几个数
     */
    public static void buildHeap(int[] arr,int n){
        int lastNode=n-1;
        int parentNode=(lastNode-1)/2;
        for(int i=parentNode;i>=0;i--){
            heapify(arr,n,i);
        }
        swap(arr,n-1,0);
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }

    public static void main(String[] args) {
//        int[] arr={105,103,6};
//        int max=0;
//        if(arr[1]>arr[max]){
//            max=1;
//        }if(arr[2]>arr[max]){
//            max=2;
//        }
//        System.out.println(arr[max]);
        int[] array = {4,5,3,1,7,2,8,10};
         heapSort(array,8);
        System.out.println(Arrays.toString(array));
    }
    public static void heapSort(int[] arr,int n){
        buildHeap(arr,n);
        for(int i=n-1;i>=2;i--){
            buildHeap(arr,i);
        }
        ArrayList<Object> objects = new ArrayList<>();
        objects.add(1);
        objects.add(2);
        System.out.println(objects.toString());

    }

}
